翻訳と辞書 Words near each other ・ Dilwale Dulhania Le Jayenge ・ Dilwale Kabhi Na Hare ・ Dilwar ・ Dilwar Hussain ・ Dilwar Khan ・ Dilwara Temples ・ Dilweg ・ Dilworth ・ Dilworth (Charlotte neighborhood) ・ Dilworth Building ・ Dilworth Elementary School (Pittsburgh, Pennsylvania) ・ Dilworth House ・ Dilworth Park ・ Dilworth School ・ Dilworth Wayne Woolley ・ Dilworth's theorem ・ Dilworth, Minnesota ・ Dilworthtown Historic District ・ Dilwyn ・ Dilwyn John ・ Dilwyn Lewis ・ Dilya Ghari Tu Sukhi Raha ・ Dilyan Kolev ・ Dilyana Popova ・ Dilys ・ Dilys Award ・ Dilys Breese ・ Dilys Breese Medal ・ Dilys Cadwaladr ・ Dilys Craven Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Dilworth's theorem ： ウィキペディア英語版 Dilworth's theorem In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician . An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. Dilworth's theorem states that there exists an antichain ''A'', and a partition of the order into a family ''P'' of chains, such that the number of chains in the partition equals the cardinality of ''A''. When this occurs, ''A'' must be the largest antichain in the order, for any antichain can have at most one element from each member of ''P''. Similarly, ''P'' must be the smallest family of chains into which the order can be partitioned, for any partition into chains must have at least one chain per element of ''A''. The width of the partial order is defined as the common size of ''A'' and ''P''. An equivalent way of stating Dilworth's theorem is that, in any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains. A version of the theorem for infinite partially ordered sets states that, in this case, a partially ordered set has finite width ''w'' if and only if it may be partitioned into ''w'' chains, but not less. == Inductive proof == The following proof by induction on the size of the partially ordered set $P$ is based on that of . Let $P$ be a finite partially ordered set. The theorem holds trivially if $P$ is empty. So, assume that $P$ has at least one element, and let $a$ be a maximal element of $P$. By induction, we assume that for some integer $k$ the partially ordered set $P\text{'}:=P\backslash setminus\backslash$ can be covered by $k$ disjoint chains $C\_1,\backslash dots,C\_k$ and has at least one antichain $A\_0$ of size $k$. Clearly, $A\_0\backslash cap\; C\_i\backslash ne\backslash emptyset$ for $i=1,2,\backslash dots,k$. For $i=1,2,\backslash dots,k$, let $x\_i$ be the maximal element in $C\_i$ that belongs to an antichain of size $k$ in $P\text{'}$, and set $A:=\backslash$. We claim that $A$ is an antichain. Let $A\_i$ be an antichain of size $k$ that contains $x\_i$. Fix arbitrary distinct indices $i$ and $j$. Then $A\_i\backslash cap\; C\_j\backslash ne\backslash emptyset$. Let $y\backslash in\; A\_i\backslash cap\; C\_j$. Then $y\backslash le\; x\_j$, by the definition of $x\_j$. This implies that $x\_i\backslash not\; \backslash ge\; x\_j$, since $x\_i\backslash not\backslash ge\; y$. By interchanging the roles of $i$ and $j$ in this argument we also have $x\_j\backslash not\backslash ge\; x\_i$. This verifies that $A$ is an antichain. We now return to $P$. Suppose first that $a\backslash ge\; x\_i$ for some $i\backslash in\backslash$. Let $K$ be the chain $\backslash \backslash cup\backslash$. Then by the choice of $x\_i$, $P\backslash setminus\; K$ does not have an antichain of size $k$. Induction then implies that $P\backslash setminus\; K$ can be covered by $k-1$ disjoint chains since $A\; \backslash setminus\; \backslash$ is an antichain of size $k\; -\; 1$ in $P\; \backslash setminus\; K$. Thus, $P$ can be covered by $k$ disjoint chains, as required. Next, if $a\backslash not\backslash ge\; x\_i$ for each $i\backslash in\backslash$, then $A\backslash cup\backslash$ is an antichain of size $k+1$ in $P$ (since $a$ is maximal in $P$). Now $P$ can be covered by the $k+1$ chains $\backslash ,C\_1,C\_2,\backslash dots,C\_k$, completing the proof. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dilworth's theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.